The present invention relates to a system and method for more efficient data management and storage on flash devices and, in particular, to a system and method in which the storage and retrieval of information on flash devices is performed through sequential write operations on sequential physical portions of the memory.
Flash devices include electrically erasable and programmable read-only memories (EEPROMs) made of flash-type, floating-gate transistors and are non-volatile memories similar in functionality and performance to EPROM memories, with an additional functionality that allows an in-circuit, programmable, operation to erase portions of the memory. Flash devices have the advantage of being relatively inexpensive and requiring relatively little power as compared to traditional magnetic storage disks. However, in a flash device, it is not practical to rewrite a previously written area of the memory without a preceding erase of the area. This limitation of flash devices causes them to be incompatible With typical existing operating system programs, since data cannot be written to an area of memory within the flash device in which data has previously been written, unless the area is first erased.
Software products have been proposed in the background art to allow a flash device to be managed by existing computer operating programs without modification of the operating system program. However, these background art programs all have deficiencies. For example, one program operates the flash memory as a xe2x80x9cwrite once read manyxe2x80x9d device. This background art software product cannot recycle previously written memory locations. When all locations are eventually written the memory cannot be further used without specific user intervention. To overcome these deficiencies of the background art, a Flash File System (FFS) was disclosed in U.S. Pat. No. 5,404,485, which is owned in common with the present application and which is hereby incorporated by reference as if fully set forth herein. FFS provided a system of data storage and manipulation on flash devices which allowed these devices to emulate magnetic disks. As noted above, the relatively inexpensive cost and low power consumption of flash devices makes them a favorable choice for data storage, particularly for laptop, portable computers. FFS enhances the ability of flash devices to act as substitutes for magnetic disk storage. Indeed, FFS as disclosed in U.S. Pat. No. 5,404,485 has proven to be so useful that the data layout specification was adopted by the PCMCIA (Personal Computer Memory Card International Association) and JEIDA (Japan Electronic Industry Development Association) committees as a standard called Flash Translation Layer (FTL).
FFS essentially describes a virtual mapping system for flash EEPROM devices. The virtual map is a table which relates the physical address of a read/write page within the flash device to the virtual address of that page. Since each of these pages is relatively small, 512 bytes, the size of the virtual map itself is quite large. FFS also includes a method of storing and maintaining the bulk of the virtual map on a flash EEPROM device, minimizing the amount of other memory required for storage of the virtual map.
As noted above, FFS has proven particularly successful for transforming flash devices into emulators of magnetic disk storage, so much so that it has been adopted as an industry standard. However, FFS cannot fulfill all of the requirements of the newer flash device technologies. In particular, FFS is not as successful with the NAND and AND flash technologies. Therefore, U.S. Pat. No. 5,937,425, which is owned in common with the present application and which is hereby incorporated by reference as if fully set forth herein, describes an additional implementation of the flash management system for these technologies. However, both of these implementations are useful mainly for specific types of technologies for flash memories.
Typical flash management systems, including the previously described systems, rely on being able to write pages in a unit in a random order, such that the first page to be written into a previously empty block is not necessarily, physically, the first page in the block but rather a page in the middle or even at the end. This sequence of data insertion can continue in any random order, as the flash devices are assumed to allow any page writing order of the pages within a block. The above management systems operate quite well with these types of flash devices.
An exception to this type of mechanism for writing data can be found in flash management systems which avoid such random insertion of data. These systems operate by allocating a new block, and copying the already written pages from the existing block into the new block, in parallel with writing the new page into that same block for every write operation. While such methods can avoid the need for a random order of page write operations by always writing the new block sequentially, they are highly inefficient when the page write requests themselves arrive in a random order, as a new block must be allocated and previous data must be copied on almost every write operation. Thus, the most efficient currently available file management systems such as FFS rely upon writing new data according to a random page order.
However, as the silicon geometries of flash devices continue to shrink, their characteristics and behavior are increasingly influenced by the smaller geometries. In particular, random page orders for writing data become increasingly less reliable for the operation of these physically more compact flash devices. Recently, a major flash manufacturer, Toshiba Inc. (Japan) announced that its next generation of NAND flash devices, using technology of the 0.16 micron process, are to require sequential page write operations within a block, rather than the insertion of data according to a random page order. As these devices are expected to be widely used in the market, there is therefore an urgent need to develop an efficient flash management system which performs only sequential write operations into the flash memory.
The background art does not teach or suggest a mechanism for the efficient management of flash devices limited to sequential page writing operations. In addition, the background art does not teach or suggest such a mechanism which does not require data to be written to a newly allocated block and for previously written pages to be moved to that new block as part of the same operation.
The present invention overcomes these deficiencies of the background art by providing a memory organization method which supports flash devices limited to sequential page write operations, such that data is written to the flash device, without requiring previously written data to be moved, and without violating the sequential write limitation.
According to the present invention, there is provided a system comprising: (a) a flash memory system comprising at least one flash device, said flash device featuring memory comprising a plurality of blocks, each block comprising a plurality of pages; (b) a flash management system for managing page write requests regardless of an order in which said page write requests are received; and (c) a module for converting said order of receiving said page write requests into a writing order, such that data in said page write requests are written as physically sequential pages within each block, regardless of said order of receiving said page write requests.
Hereinafter, the term xe2x80x9cphysical unitxe2x80x9d is defined as a unit on the physical media or hardware of the memory which is the smallest portion of the memory which can be erased or an integral multiple thereof It is a portion of the memory which is contiguous, fixed in size and erasable.
The term xe2x80x9cpagexe2x80x9d is hereinafter defined as the smallest chunk of data to be written in one operation. The terms xe2x80x9cblockxe2x80x9d and xe2x80x9cunitxe2x80x9d are defined as the same size as the physical unit, with a block containing one or more pages.
Hereinafter, the term xe2x80x9cvirtual unitxe2x80x9d is defined as the same size as the physical unit.
Hereinafter, the term xe2x80x9cvirtual mapxe2x80x9d refers to a table which relates a virtual block or page to at least one corresponding physical block or page.
Hereinafter, the term xe2x80x9cwriting dataxe2x80x9d describes the act of storing data on the flash memory. The term xe2x80x9creading dataxe2x80x9d describes the act of retrieving data from the flash memory. Hereinafter, the term xe2x80x9cunwrittenxe2x80x9d indicates some portion of the memory, such as a physical block, which is capable of having data written to it. Thus, the term xe2x80x9cunwrittenxe2x80x9d includes, but is not limited to, a portion of the memory which has just been erased.
In a computer or other electronic device having a flash memory organized according to the present invention, the operating system of that device interacts with the virtual units and virtual pages for reading and writing data. The virtual media, which includes the virtual units and pages, thus acts as an interface for the operating system to interact with the flash memory device. For example, the operating system issues a write command to write data to a virtual page. The virtual unit containing the virtual page is then located. The virtual map then locates a corresponding physical page within a physical unit of the memory, where the data are actually stored. Although the operating system issues read and write commands as though the virtual units and virtual pages are the actual hardware of the flash memory, in reality the actual hardware is incorporated in the physical units and physical pages of the flash memory. Thus, the operating system is only aware of the virtual units and pages, and does not directly interact with the hardware itself The advantage of such an interface is that the inherent disadvantages of the flash memory, such as the requirement for performing an erase operation before further writing can occur, are overcome by the interactions of the operating system with the virtual addresses rather than the physical addresses.